//
//  Heap.c
//  堆排序的初步实现
//
//  Created by Yan Zihao on 2024/11/21.
//
#include "Heap.h"
void HeapInit(Heap* php)
{
    assert(php);
    php->_a = NULL;
    php->_size = php->_capacity = 0;
}

void HeapDestory(Heap* hp)
{
    assert(hp);
    free(hp->_a);
    hp->_a = NULL;
    hp->_capacity = hp->_size = 0;
}

void Swap(HPDataType* a, HPDataType* b)
{
    HPDataType tmp = *a;
    *a = *b;
    *b = tmp;
}

void AdjustUp(HPDataType* a, HPDataType child)
{
    HPDataType parent = (child - 1) / 2;
    
    while (child > 0)
    {
        if (a[parent] > a[child])
        {
            Swap(&a[parent], &a[child]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }

}

void HeapPush(Heap* hp, HPDataType x)
{
    assert(hp);
    if (hp->_size == hp->_capacity)
    {
        int newcapacity = hp->_capacity == 0 ? 4 : 2*(hp->_capacity);
        HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType)*newcapacity);
        if (tmp == NULL)
        {
            perror("realloc fail");
            return;
        }
        hp->_a = tmp;
        hp->_capacity = newcapacity;
    }
    hp->_a[hp->_size++] = x;
    AdjustUp(hp->_a, hp->_size - 1);
}

void AdjustDown(HPDataType* a ,HPDataType parent, int n)
{
    HPDataType child = parent * 2 + 1;
    while(child < n)
    {
        if (child + 1 < n && a[child + 1] < a[child])
        {
            child++;
        }
        
        if (a[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        
        else
        {
            break;
        }
    }

}

void HeapPop(Heap* hp)
{
    assert(hp);
    assert(hp->_size > 0);
    Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
    hp->_size--;
    AdjustDown(hp->_a, 0, hp->_size);
}

int main(void)
{
    int arr[] = {3,6,2,7,4};
    Heap HP;
    HeapInit(&HP);
    int n = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < n; i++)
    {
        HeapPush(&HP, arr[i]);
    }
    HeapPop(&HP);
    for (int i = 0; i < HP._size; i++)
    {
        printf("%d ",HP._a[i]);
    }
    
    return 0;
}

HPDataType HPTop(Heap* php)
{
    assert(php);
    assert(php->_size > 0);

    return php->_a[0];
}

bool HPEmpty(Heap* php)
{
    assert(php);

    return php->_size == 0;
}
